package airthmetic.exercise.greedy;

import java.util.Arrays;

public class _322_零钱兑换 {
    static int resMin = Integer.MAX_VALUE;
    public static int coinChange(int[] coins, int amount) {
        // 贪心 + 回溯
        // 对硬币coins进行倒序排序
        // 进行dfs回溯，参数coins amount startIndex , resAmount, 另外维护一个全局的成员变量，用来记录最小值
        // 如果dfs回溯完成后最小值还为初始值  此时返回-1
        sort(coins);
//        dfs(coins, amount,0,0);
        dfs2(coins, amount,0,0);
        if(resMin == Integer.MAX_VALUE){
            return -1;
        }

        return resMin;
    }

    public static void dfs(int[] coins, int amount, int startIndex, int selectedCount){
        if(amount == 0){
            if(selectedCount < resMin){
                resMin = selectedCount;
            }
            return;
        }
        if(startIndex >= coins.length){
            return;
        }

        int maxCount = amount / coins[startIndex];
        for(int i=maxCount; i >= 0 && i+selectedCount < resMin;  i--){
            int drillAmount =  amount - (coins[startIndex] * i);

            dfs(coins,drillAmount,startIndex+1, selectedCount+i);
        }
    }

    // 纯回溯
    public static void dfs2(int[] coins, int amount, int startIndex, int selectedCount){
        // terminal
        if(amount == 0){
            if(selectedCount < resMin){
                resMin = selectedCount;
            }
            return;
        }
        if(startIndex >= coins.length){
            return;
        }

        // process current logic
        for(int i=coins.length; i >= 0 && selectedCount < resMin;  i--){
            int drillAmount =  amount - coins[startIndex];
            // 剪枝
            if(drillAmount < 0){
                continue;
            }
            // drill down
            dfs2(coins,drillAmount,i, selectedCount+1);
        }
    }


    public static void sort(int[] coins){
        int n = coins.length - 1;
        Arrays.sort(coins);
        for(int i=0; i<= (n - 1) / 2; i++){
            int temp = coins[i];
            coins[i] = coins[n - i];
            coins[n - i] = temp;
        }
    }


    public static void main(String[] args) {
        int[] dan = new int[]{1,2,3,4,5};
        int[] shuang = new int[]{1,2,3,4};
        sort(dan);
        System.out.println("==================================");
        sort(shuang);
        System.out.println("排序测试结束=======================================================");

        // 边界值测试
        int[] coins4 = new int[]{411,412,413,414,415,416,417,418,419,420,421,422};
//        int[] coins = new int[]{1,2,18,50};
//        int[] coins2 = new int[]{1,2,5};
//        int amount = 120;
        int amount4 = 9864;
//        int amount2 = 11;
//        System.out.println(coinChange(coins2, amount2));
//        System.out.println(coinChange(coins, amount));
//        System.out.println(coinChange(coins4, amount4));
        System.out.println(coinChange3(coins4, amount4));

    }



    public static int coinChange3(int[] coins, int amount) {
        /*
        * 动态规划思考问题
        *
        * 1.确定状态参数/状态和选择
        *   状态  在子问题与原问题之间变化的值  此题为amount
        *   选择/决策 做选择会让状态变更并且逐渐趋近于原问题
        *     for(int coin : coins){
        *     }
        * 2.定义dp数组(dp table)的含义： 子问题需要缓存起来在后续使用，一般dp数组中存储的值就是我们问题需要返回的结果。
        *   dp[i]: 如果能从coins中找到对应的硬币个数凑成金额i,那么所需要的最少硬币个数即dp[i]的值
        * 3.确定初始状态的值
        *   dp[0] = 0;
        * 4.确定状态转移的逻辑 （状态转移公式） 怎么根据子问题求解求解原问题
        *   在这一步我们动态规划的思想是：通过子问题的解来推导原问题的解
        *   也就是说：如果你已经计算出dp[0],dp[1]...dp[i-2],dp[i-1]的值之后，你如何去计算出dp[i]的值
        *   当然这个过程是通过我们做选择来让状态发生转移的
        *   此处的状态转移公式为
        *    for(int coin : coins){
        *       dp[i] = dp[i-coin] + coin (dp[i-coin] + 1)
        *       dp[i] = Math.min(dp[i], dp[i-coin] + 1);
        *   }
        * */



        //构造dp数组(缓存中间的状态信息/子问题的最优解/状态参数的值)
        int[] dp = new int[amount+1];
        //初始填充一个不可能的值,对应面额amount最多的组合就是amount个1的组合，需要
        //amount个硬币,所以amount+1是不可能的
        Arrays.fill(dp,amount+1);
        //初始状态赋值
        dp[0] = 0;//amount=0无需硬币组合
        // 对每种状态的每种取值进行遍历
        //从子问题开始求解,推导到大问题，外层循环遍历所有状态的所有取值
        for (int i=1;i<=amount;i++) {
        //对每个子问题i，在coins中找能满足子问题i的众多解中的最优解(最少硬币数量)，
            //内层 for 循环在求所有选择的最小值
            for (int coin:coins) {
                if (coin <= i) { //coin>子问题i，该硬币无法构成最终解,直接跳过
                    /*
                    1:直接从dp中拿出求解问题i所依赖的子问题(i-coin)的最优解,
                    2:dp[i-coin] + 1即当前子问题i选择该coin的最优解
                    3:dp[i] = Math.min(dp[i],dp[i-coin]+1);是在众多解中选出一个
                    最优的作为子问题i的最优解。
                    */
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }

        return (dp[amount]==amount+1) ? -1:dp[amount];
    }


}
